class Solution3 {

    int[][] meo;

    public int getMoneyAmount(int n) {
        meo = new int[n + 1][n + 1];
        return dfs(1, n);
    }

    public int dfs(int left, int right){
        if(left >= right) { return 0;}
        if(meo[left][right] != 0) { return meo[left][right];}

        int ret = Integer.MAX_VALUE;
        for(int head = left; head <= right; head++){
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = Math.min(ret, Math.max(x, y) + head);
        }
        meo[left][right] = ret;
        return ret;
    }
}